/*
 *  linux/fs/buffer.c
 *
 *  (C) 1991  Linus Torvalds
 */

/*
 *  'buffer.c' implements the buffer-cache functions. Race-conditions have
 * been avoided by NEVER letting a interrupt change a buffer (except for the
 * data, of course), but instead letting the caller do it. NOTE! As interrupts
 * can wake up a caller, some cli-sti sequences are needed to check for
 * sleep-on-calls. These should be extremely quick, though (I hope).
 */

/*
 * NOTE! There is one discordant note here: checking floppies for
 * disk change. This is where it fits best, I think, as it should
 * invalidate changed floppy-disk-caches.
 */

#include "../include/linux/sched.h"
#include "../include/asm/system.h"
#include "../include/stdarg.h"

//end is a symbol that is defined by the linker. It represents the end of the kernel image in memory.
extern int end;

extern void put_super(int);

extern void invalidate_inodes(int);

struct buffer_head *start_buffer = (struct buffer_head *) &end;
struct buffer_head *hash_table[NR_HASH];
static struct buffer_head *free_list;
static struct task_struct *buffer_wait = NULL;
int NR_BUFFERS = 0;

static inline void wait_on_buffer(struct buffer_head *bh) {
    cli();
    while (bh->b_lock)
        sleep_on(&bh->b_wait);
    sti();
}

int sys_sync(void) {
    int i;
    struct buffer_head *bh;

    sync_inodes();        /* write out inodes into buffers */
    bh = start_buffer;
    for (i = 0; i < NR_BUFFERS; i++, bh++) {
        wait_on_buffer(bh);
        if (bh->b_dirt)
            ll_rw_block(WRITE, bh);
    }
    return 0;
}
////对指定设备进行高速缓冲数据与设备上数据的同步操作。
// 该函数首先搜索高速缓冲区中所有缓冲块。
// 对于指定设备 dev 的缓冲块，若其数据已被修改过就写入盘中（同步操作）。
// 然后把内存中i节点表数据写入高速缓冲中。
// 之后再对指定设备 dev 执行一次与上述相同的写盘操作。
int sync_dev(int dev) {
    int i;
    struct buffer_head *bh;

    //bh 指向高速缓冲区开始处
    bh = start_buffer;
    // 扫描高速缓冲区中所有缓冲块，对指定设备 dev 的缓冲块，
    for (i = 0; i < NR_BUFFERS; i++, bh++) {
        if (bh->b_dev != dev)
            continue;
        // 先检测其是否己被上锁，若己被上锁就睡眠等待其解锁。
        wait_on_buffer(bh);
        // 睡眠期间该缓冲块有可能已被释放或者被挪作它用，所以再判断一次该缓冲块是否还是指定设备的缓冲块并且 已修改过（b_dirt 标志置位）
        if (bh->b_dev == dev && bh->b_dirt)
            ll_rw_block(WRITE, bh);
    }
    //再将i节点数据写入高速缓冲。让i节点表 inode_table 中的 inode 与缓冲中的信息同步。
    //i节点是存储在内存的虚拟盘，硬盘的数据缓冲是在高速缓冲区，要真正写盘，是需要先写到高速缓冲区，再写到硬盘
    sync_inodes();
    // 然后在高速缓冲中的数据更新之后，再把它们与设备中的数据同步。
    // 这里采用两遍同步操作是为了提高内核执行效率。第一遍缓冲区同步操作可以让内核中许多“脏块”变干净，
    // 使得i节点的同步操作能够高效执行。本次缓冲区同步操作则把那些由于i节点同步操作而又变脏的缓冲块与设备中数据同步。
    bh = start_buffer;
    for (i = 0; i < NR_BUFFERS; i++, bh++) {
        if (bh->b_dev != dev)
            continue;
        wait_on_buffer(bh);
        if (bh->b_dev == dev && bh->b_dirt)
            ll_rw_block(WRITE, bh);
    }
    return 0;
}

static void inline invalidate_buffers(int dev) {
    int i;
    struct buffer_head *bh;

    bh = start_buffer;
    for (i = 0; i < NR_BUFFERS; i++, bh++) {
        if (bh->b_dev != dev)
            continue;
        wait_on_buffer(bh);
        if (bh->b_dev == dev)
            bh->b_uptodate = bh->b_dirt = 0;
    }
}

/*
 * This routine checks whether a floppy has been changed, and
 * invalidates all buffer-cache-entries in that case. This
 * is a relatively slow routine, so we have to try to minimize using
 * it. Thus it is called only upon a 'mount' or 'open'. This
 * is the best way of combining speed and utility, I think.
 * People changing diskettes in the middle of an operation deserve
 * to loose :-)
 *
 * NOTE! Although currently this is only for floppies, the idea is
 * that any additional removable block-device will use this routine,
 * and that mount/open needn't know that floppies/whatever are
 * special.
 */
void check_disk_change(int dev) {
    int i;

    if (MAJOR(dev) != 2)
        return;
    if (!floppy_change(dev & 0x03))
        return;
    for (i = 0; i < NR_SUPER; i++)
        if (super_block[i].s_dev == dev)
            put_super(super_block[i].s_dev);
    invalidate_inodes(dev);
    invalidate_buffers(dev);
}

#define _hashfn(dev, block) (((unsigned)(dev^block))%NR_HASH)
#define hash(dev, block) hash_table[_hashfn(dev,block)]

static inline void remove_from_queues(struct buffer_head *bh) {
/* remove from hash-queue */
    if (bh->b_next)
        bh->b_next->b_prev = bh->b_prev;
    if (bh->b_prev)
        bh->b_prev->b_next = bh->b_next;
    if (hash(bh->b_dev, bh->b_blocknr) == bh)
        hash(bh->b_dev, bh->b_blocknr) = bh->b_next;
/* remove from free list */
    if (!(bh->b_prev_free) || !(bh->b_next_free))
        panic("Free block list corrupted");
    bh->b_prev_free->b_next_free = bh->b_next_free;
    bh->b_next_free->b_prev_free = bh->b_prev_free;
    if (free_list == bh)
        free_list = bh->b_next_free;
}

static inline void insert_into_queues(struct buffer_head *bh) {
/* put at end of free list */
    bh->b_next_free = free_list;
    bh->b_prev_free = free_list->b_prev_free;
    free_list->b_prev_free->b_next_free = bh;
    free_list->b_prev_free = bh;
/* put the buffer in new hash-queue if it has a device */
    bh->b_prev = NULL;
    bh->b_next = NULL;
    if (!bh->b_dev)
        return;
    bh->b_next = hash(bh->b_dev, bh->b_blocknr);
    hash(bh->b_dev, bh->b_blocknr) = bh;
    bh->b_next->b_prev = bh;
}

static struct buffer_head *find_buffer(int dev, int block) {
    struct buffer_head *tmp;

    for (tmp = hash(dev, block); tmp != NULL; tmp = tmp->b_next)
        if (tmp->b_dev == dev && tmp->b_blocknr == block)
            return tmp;
    return NULL;
}

/*
 * Why like this, I hear you say... The reason is race-conditions.
 * As we don't lock buffers (unless we are readint them, that is),
 * something might happen to it while we sleep (ie a read-error
 * will force it bad). This shouldn't really happen currently, but
 * the code is ready.
 */
struct buffer_head *get_hash_table(int dev, int block) {
    struct buffer_head *bh;

    for (;;) {
        if (!(bh = find_buffer(dev, block)))
            return NULL;
        bh->b_count++;
        wait_on_buffer(bh);
        if (bh->b_dev == dev && bh->b_blocknr == block)
            return bh;
        bh->b_count--;
    }
}

/*
 * Ok, this is getblk, and it isn't very clear, again to hinder
 * race-conditions. Most of the code is seldom used, (ie repeating),
 * so it should be much more efficient than it looks.
 *
 * The algoritm is changed: hopefully better, and an elusive bug removed.
 */
#define BADNESS(bh) (((bh)->b_dirt<<1)+(bh)->b_lock)

struct buffer_head *getblk(int dev, int block) {
    struct buffer_head *tmp, *bh;

    repeat:
    if ((bh = get_hash_table(dev, block)))
        return bh;
    tmp = free_list;
    do {
        //如果该缓冲区正被使用（引用计数不等于0），则继续扫描下一项。
        if (tmp->b_count)
            continue;
        // 对于 b_count=0 的块，即高速缓冲中当前没有引用的块，不一定就是干净的（b_dirt=0）或没有锁定的(b_lock=0)
        // 因此，我们还是需要继续下面的判断和选择。例如当一个任务改写过一块内容后就释放了，于是该块b_count= 0，但b_lock 不等于0；
        // 当一个任务执行 breada ()预读几个块时，只要ll_rw_block() 命令发出后，它就会递减b_count,
        // 但此时实际上硬盘访问操作可能还在进行， 因此此时 b_lock=1，但 bcount=0。

        //如果缓冲头指针 bh 为空，或者 tmp 所指缓冲头的标志(修改、锁定)权重小于 bh 头标志的权重，则让 bh指向 tmp缓冲块头。
        if (!bh || BADNESS(tmp) < BADNESS(bh)) {
            bh = tmp;
            // 如果 tmp缓冲块 既没有修改也没有锁定标志置位，就使用该块，则退出循环。
            if (!BADNESS(tmp))
                break;
        }
        // 否则我们就继续执行本循环，看看能否找到一个 BADNESS() 最小的缓冲快。
/* and repeat until we find something good */
    } while ((tmp = tmp->b_next_free) != free_list);
    //如果循环检查发现所有缓冲块都正在被使用（所有缓冲块的b_count>0）中，
    if (!bh) {
        // 则睡眠等待有空闲缓冲块可用。当有空闲缓冲块可用时本进程会被明确地唤醒,从repeat开始执行
        sleep_on(&buffer_wait);
        goto repeat;
    }
    wait_on_buffer(bh);
    if (bh->b_count)
        goto repeat;

    //如果该缓冲区己被修改，
    while (bh->b_dirt) {
        //将数据写盘
        sync_dev(bh->b_dev);
        //等待缓冲区解锁
        wait_on_buffer(bh);
        // 若该缓冲区又被其他任务使用的话，只好再重复上述寻找过程。
        if (bh->b_count)
            goto repeat;
    }
/* NOTE!! While we slept waiting for this block, somebody else might */
/* already have added "this" block to the cache. check it */
    if (find_buffer(dev, block))
        goto repeat;
/* OK, FINALLY we know that this buffer is the only one of it's kind, */
/* and that it's unused (b_count=0), unlocked (b_lock=0), and clean */
    bh->b_count = 1;
    bh->b_dirt = 0;
    bh->b_uptodate = 0;
    //把当前块从队列中移除
    remove_from_queues(bh);
    bh->b_dev = dev;
    bh->b_blocknr = block;
    //把当前块添加到freeList队列的末尾
    insert_into_queues(bh);
    return bh;
}

void brelse(struct buffer_head *buf) {
    if (!buf)
        return;
    wait_on_buffer(buf);
    if (!(buf->b_count--))
        panic("Trying to free free buffer");
    wake_up(&buffer_wait);
}

/*
 * bread() reads a specified block and returns the buffer that contains
 * it. It returns NULL if the block was unreadable.
 */
struct buffer_head *bread(int dev, int block) {
    struct buffer_head *bh;

    if (!(bh = getblk(dev, block)))
        panic("bread: getblk returned NULL\n");
    if (bh->b_uptodate)
        return bh;
    ll_rw_block(READ, bh);
    wait_on_buffer(bh);
    if (bh->b_uptodate)
        return bh;
    brelse(bh);
    return NULL;
}

#define COPYBLK(from, to) \
__asm__("cld\n\t" \
    "rep\n\t" \
    "movsl\n\t" \
    ::"c" (BLOCK_SIZE/4),"S" (from),"D" (to) \
    )

/*
 * bread_page reads four buffers into memory at the desired address. It's
 * a function of its own, as there is some speed to be got by reading them
 * all at the same time, not waiting for one to be read, and then another
 * etc.
 */
void bread_page(unsigned long address, int dev, int b[4]) {
    struct buffer_head *bh[4];
    int i;

    for (i = 0; i < 4; i++)
        if (b[i]) {
            if ((bh[i] = getblk(dev, b[i])))
                if (!bh[i]->b_uptodate)
                    ll_rw_block(READ, bh[i]);
        } else
            bh[i] = NULL;
    for (i = 0; i < 4; i++, address += BLOCK_SIZE)
        if (bh[i]) {
            wait_on_buffer(bh[i]);
            if (bh[i]->b_uptodate)
                    COPYBLK((unsigned long) bh[i]->b_data, address);
            brelse(bh[i]);
        }
}

/*
 * Ok, breada can be used as bread, but additionally to mark other
 * blocks for reading as well. End the argument list with a negative
 * number.
 */
/**
 * 从指定设备读取指定的一些块。
 * 函数参数个数可变，是一系列指定的块号。成功时返回第1块的缓冲块头指针，否则返回 NULL。
 * @param dev
 * @param first
 * @param ...
 * @return
 */
struct buffer_head *breada(int dev, int first, ...) {
    // This variable is used to store and manage information about the `...`variable arguments
    va_list args;
    struct buffer_head *bh, *tmp;
    //把 `first` 和 `...` 拼接到参数args中
    va_start(args, first);
    //首先取可变参数表中第1个参数（块号）。接着从高速缓冲区中取指定设备和块号的缓冲块。
    if (!(bh = getblk(dev, first)))
        panic("bread: getblk returned NULL\n");
    //如果该缓冲块数据无效（更新标志未置位），则发出读设备数据块请求。
    if (!bh->b_uptodate)
        ll_rw_block(READ, bh);
    //use the va_arg macro to extract arguments one by one,
    while ((first = va_arg(args, int)) >= 0) {
        tmp = getblk(dev, first);
        if (tmp) {
            if (!tmp->b_uptodate)
                ll_rw_block(READA, tmp);
            //因为这里是预读随后的数据块，只需读进高速缓冲区但并不是马上就使用，所以第337 行语
            //句需要将其引用计数递减释放掉该块（因为 getblk(） 函数会增加引用计数值）。
            tmp->b_count--;
        }
    }
    //`va_end` to clean up the memory allocated for the `va_list`.
    va_end(args);
    //此时可变参数表中所有参数处理完毕。于是等待第1个缓冲区解锁（如果己被上锁）。
    //在等待退出之后如果缓冲区中数据仍然有效，则返回缓冲区头指针退出。否则释放该缓冲区返回NULL，退出。
    wait_on_buffer(bh);
    if (bh->b_uptodate)
        return bh;
    brelse(bh);
    return (NULL);
}

void buffer_init(long buffer_end) {
    struct buffer_head *h = start_buffer;
    void *b;
    int i;

    if (buffer_end == 1 << 20)
        b = (void *) (640 * 1024);
    else
        b = (void *) buffer_end;
    while ((b -= BLOCK_SIZE) >= ((void *) (h + 1))) {
        h->b_dev = 0;
        h->b_dirt = 0;
        h->b_count = 0;
        h->b_lock = 0;
        h->b_uptodate = 0;
        h->b_wait = NULL;
        h->b_next = NULL;
        h->b_prev = NULL;
        h->b_data = (char *) b;
        h->b_prev_free = h - 1;
        h->b_next_free = h + 1;
        h++;
        NR_BUFFERS++;
        if (b == (void *) 0x100000)
            b = (void *) 0xA0000;
    }
    h--;
    free_list = start_buffer;
    free_list->b_prev_free = h;
    h->b_next_free = free_list;
    for (i = 0; i < NR_HASH; i++)
        hash_table[i] = NULL;
}	